#include "temu.h"

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <stdlib.h>
#include <sys/types.h>
#include <regex.h>

enum
{
	NOTYPE = 256,
	EQ = 20,
	PLUS = 30,
	SUB = 31,
	MUL = 40,
	LEFT_BRACKET = 257,
	RIGHT_BRACKET = 258,
	DIV = 41,
	DEC = 259,
	NEGATE = 50,
	HEX = 260,
	REG = 261,
	DEREF = 51,
	NOT = 52,
	NEQ = 21,
	AND = 10,
	OR = 11
	/* TODO: Add more token types */

};

// struct rule 包含了正则表达式和标记类型的规则
static struct rule
{
	char *regex;
	int token_type;
} rules[] = {

	/* TODO: Add more rules.
	 * Pay attention to the precedence level of different rules.
	 */

	{" +", NOTYPE}, // spaces
	{"\\+", PLUS},	// plus
	{"==", EQ},		// equal
	{"-", SUB},
	{"\\*", MUL},
	{"\\(", LEFT_BRACKET},
	{"\\)", RIGHT_BRACKET},
	{"/", DIV},
	{"[1-9][0-9]*", DEC},
	{"0x?[0-9a-fA-F]*", HEX},
	{"\\$(zero||ra||[tf]p||s[p0-8]||a[0-7]||t[0-8]||x||pc)", REG},
	{"!=", NEQ},
	{"!", NOT},
	{"&&", AND},
	{"\\|\\|", OR}};

#define NR_REGEX (sizeof(rules) / sizeof(rules[0]))

static regex_t re[NR_REGEX];

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex()
{
	int i;
	char error_msg[128];
	int ret;

	for (i = 0; i < NR_REGEX; i++)
	{
		ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
		if (ret != 0)
		{
			regerror(ret, &re[i], error_msg, 128);
			Assert(ret == 0, "regex compilation failed: %s\n%s", error_msg, rules[i].regex);
		}
	}
}

typedef struct token
{
	int type;
	char str[32];
} Token;

Token tokens[32];
int nr_token;

// 它负责将输入字符串 e 分解为标记并存储在 tokens 数组中
static bool make_token(char *e)
{
	// 它用于跟踪在输入字符串中的当前位置，开始为 0
	int position = 0;
	int i;
	regmatch_t pmatch;

	nr_token = 0;

	// 使用 while 循环遍历输入字符串 e，直到字符串的结尾
	while (e[position] != '\0')
	{
		/* Try all rules one by one. */
		for (i = 0; i < NR_REGEX; i++)
		{
			// 在循环中，通过迭代 rules 数组来匹配可能的标记。如果正则表达式匹配成功，且匹配的字符串在字符串的起始位置（pmatch.rm_so 为 0），则进行如下操作
			if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0)
			{
				// 存储匹配的子字符串的起始地址
				char *substr_start = e + position;
				// 存储匹配的子字符串的长度
				int substr_len = pmatch.rm_eo;

				Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s", i, rules[i].regex, position, substr_len, substr_len, substr_start);
				position += substr_len;

				/* TODO: Now a new token is recognized with rules[i]. Add codes
				 * to record the token in the array `tokens'. For certain types
				 * of tokens, some extra actions should be performed.
				 */

				switch (rules[i].token_type)
				{
				case NOTYPE:
					break;
				case PLUS:
					tokens[nr_token++].type = PLUS;
					break;
				case EQ:
					tokens[nr_token++].type = EQ;
					break;
				case SUB:
					tokens[nr_token++].type = SUB;
					break;
				case MUL:
					tokens[nr_token++].type = MUL;
					break;
				case LEFT_BRACKET:
					tokens[nr_token++].type = LEFT_BRACKET;
					break;
				case RIGHT_BRACKET:
					tokens[nr_token++].type = RIGHT_BRACKET;
					break;
				case DIV:
					tokens[nr_token++].type = DIV;
					break;
				case DEC:
				{
					tokens[nr_token].type = DEC;
					strncpy(tokens[nr_token].str, substr_start, substr_len);
					tokens[nr_token++].str[substr_len] = '\0';
					break;
				}
				case HEX:
				{
					tokens[nr_token].type = HEX;
					strncpy(tokens[nr_token].str, substr_start, substr_len);
					tokens[nr_token++].str[substr_len] = '\0';
					break;
				}
				case REG:
				{
					tokens[nr_token].type = REG;
					strncpy(tokens[nr_token].str, substr_start, substr_len);
					tokens[nr_token++].str[substr_len] = '\0';
					break;
				}
				case NOT:
					tokens[nr_token++].type = NOT;
					break;
				case NEQ:
					tokens[nr_token++].type = NEQ;
					break;
				case AND:
					tokens[nr_token++].type = AND;
					break;
				case OR:
					tokens[nr_token++].type = OR;
					break;
				default:
					panic("please implement me");
				}

				break;
			}
		}
		// 如果在循环结束后 i 仍然等于 NR_REGEX，表示没有匹配到任何规则，
		// 那么会打印错误信息，指示在哪个位置未匹配成功，并返回 false。
		if (i == NR_REGEX)
		{
			printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
			return false;
		}
	}

	return true;
}

bool check_parentheses(int p, int q)
{
	if (tokens[p].type != LEFT_BRACKET)
		return false;
	int LEFT_BRACKET_NUM = 0;
	int RIGHT_BRACKET_NUM = 0;
	int subnum = 0;
	bool zero = false;
	for (int i = p; i < q; i++)
	{
		if (tokens[i].type == LEFT_BRACKET)
			LEFT_BRACKET_NUM++;
		else if (tokens[i].type == RIGHT_BRACKET)
			RIGHT_BRACKET_NUM++;
		subnum = LEFT_BRACKET_NUM - RIGHT_BRACKET_NUM;
		if (subnum == 0)
			zero = true;
	}
	if (subnum > 1 || (subnum == 1 && tokens[q].type != RIGHT_BRACKET) || subnum < 0)
	{
		panic("please implement me");
	}
	else if (subnum == 1 && tokens[q].type == RIGHT_BRACKET && zero == false)
		return true;
	else
		return false;
}

int findop(int p, int q)
{
	int op = p;
	int LEFT_BRACKET_NUM = 0;
	int RIGHT_BRACKET_NUM = 0;
	int subnum = 0;
	for (int i = p; i <= q; i++)
	{
		if (tokens[i].type == LEFT_BRACKET)
			LEFT_BRACKET_NUM++;
		else if (tokens[i].type == RIGHT_BRACKET)
			RIGHT_BRACKET_NUM++;
		subnum = LEFT_BRACKET_NUM - RIGHT_BRACKET_NUM;
		if (tokens[i].type / 10 >= 1 && tokens[i].type / 10 <= 5 && subnum == 0)
		{
			if (tokens[i].type / 10 <= tokens[op].type / 10)
				op = i;
		}
	}
	return op;
}
uint32_t eval(int p, int q)
{
	if (p > q)
	{
		if (tokens[p].type == NEGATE || tokens[p].type == DEREF || tokens[p].type == NOT)
			return 0;
		else
			panic("please implement me");
	}
	else if (p == q)
	{
		char *endptr;
		if (tokens[p].type == DEC)
			return strtoul(tokens[p].str, &endptr, 10);
		else if (tokens[p].type == HEX)
			return strtoul(tokens[p].str, &endptr, 16);
		else
		{
			const char *regfile[] = {"$zero", "$ra", "$tp", "$sp", "$a0",
									 "$a1", "$a2", "$a3", "$a4", "$a5",
									 "$a6", "$a7", "$t0", "$t1", "$t2",
									 "$t3", "$t4", "$t5", "$t6", "$t7",
									 "$t8", "$x", "$fp", "$s0", "$s1",
									 "$s2", "$s3", "$s4", "$s5", "$s6",
									 "$s7", "$s8", "$pc"};
			for (int i = 0; i < 33; i++)
			{
				if (strcmp(tokens[p].str, regfile[i]) == 0)
				{
					if (i == 32)
						return cpu.pc;
					else
						return reg_w(i);
				}
			}
			panic("please implement me");
		}
	}
	else if (check_parentheses(p, q) == true)
	{
		return eval(p + 1, q - 1);
	}
	else
	{
		int op = findop(p, q);
		uint32_t val1 = eval(p, op - 1);
		uint32_t val2 = eval(op + 1, q);
		switch (tokens[op].type)
		{
		case PLUS:
			return val1 + val2;
			break;
		case SUB:
			return val1 - val2;
			break;
		case MUL:
			return val1 * val2;
			break;
		case DIV:
			return val1 / val2;
			break;
		case NEGATE:
			return val1 - val2;
			break;
		case DEREF:
		{
			uint32_t addr = val2 & 0x7FFFFFFF;
			uint32_t result = mem_read(addr, 4);
			return result;
			break;
		}
		case NOT:
			return !val2;
			break;
		case EQ:
			return val1 == val2;
			break;
		case NEQ:
			return val1 != val2;
			break;
		case AND:
			return val1 && val2;
			break;
		case OR:
			return val1 || val2;
			break;
		default:
			assert(0);
		}
	}
}
uint32_t expr(char *e, int *success)
{
	if (!make_token(e))
	{
		success = false;
		return 0;
	}

	/* TODO: Insert codes to evaluate the expression. */
	// panic("please implement me");
	for (int i = 0; i < nr_token; i++)
	{
		if (tokens[i].type == SUB && (i == 0 || (tokens[i - 1].type != DEC && tokens[i - 1].type != HEX && tokens[i - 1].type != REG)))
			tokens[i].type = NEGATE;
		if (tokens[i].type == MUL && (i == 0 || (tokens[i - 1].type != DEC && tokens[i - 1].type != HEX && tokens[i - 1].type != REG)))
			tokens[i].type = DEREF;
	}
	return eval(0, nr_token - 1);
}
